データの順列演算を実行するための装置および方法

专利摘要:
順列演算を実行するための順列回路を有する処理回路と、データを格納するための複数のレジスタを有するレジスタバンクと、プログラム命令に応答して処理回路を制御し、データ処理演算を実行する制御回路と、を含む処理データのための装置が提供される。制御回路は、制御生成命令に応答して、ビットマスクに基づいて制御信号を生成し、入力オペランドに対して順列演算を実行するための順列回路を構成するように構成される。ビットマスクは、第１の順序を有する第１のグループのデータ要素と第２の順序を有する第２のグループのデータ要素とを前記入力オペランド内で特定し、順列演算は、前記第１の順序と前記第２の順序とのうちの一方を保存するが、前記第１の順序と前記第２の順序とのうちの他方を変える。
公开号:JP2011510389A
申请号:JP2010542674
申请日:2008-11-26
公开日:2011-03-31
发明作者:ドミニク・ヒューゴ・サイムス；ムラデン・ワイルダー
申请人:アーム・リミテッド；
IPC主号:G06F17-16

专利说明:

[0001] 本発明は、データの順列演算を実行するための装置と方法とに関する。]
背景技術

[0002] 信号処理アプリケーションなどのデータ処理アプリケーションは、一般に、データの再配置が高データレートで実行される必要がある。例えば、単一命令多重データ（ＳＩＭＤ）エンジンの使用時など、データ処理が十分に加速されると、順列化などのデータ再配置が、計算を実行する際のボトルネックになることがある。]
[0003] 無線標準規格で使用される信号処理アプリケーションなどでは、デインターリーブ演算とインターリーブ演算とが、極めて一般的な順列化の形態である。これらの演算は、デインターリーブの場合には２つ以上のチャネルを分離する目的で、インターリーブの場合には２本以上のチャネルを結合する目的で実行される。パイロットチャネル（すなわち制御チャネル）からのデータチャネルの分離はその一例である。誤り訂正は、ノイズのある通信チャネルを介したデータ伝送を理由に発生し得る誤りを訂正するために、信号処理で広く使用されている。誤り訂正処理時には、データのパンクチャリングとデパンクチャリングが実行されることが多い。パンクチャリングは、データレートと誤り耐性との間のトレードオフを変える目的で使用される。パンクチャリング動作がデータチャネルをデインターリーブして第２のチャネルを破棄することを伴うのに対し、デパンクチャリングは、ゼロを有する１つの通信チャネルをインターリーブすることを伴う。]
[0004] 複数のバタフライ順列ネットワークを並行使用してデインターリーブ演算を実行することは公知である。例えば、Ｙ． Ｈｉｌｅｗｉｔｚ、Ｚ． Ｓｈｅｅ、およびＲ Ｌｅｅによる「Ｃｏｍｐａｒｉｎｇ Ｆａｓｔ Ｉｍｐｌｅｍｅｎｔａｔｉｏｎｓ ｏｆ Ｂｉｔ Ｐｅｒｍｕｔａｔｉｏｎ Ｉｎｓｔｒｕｃｔｉｏｎｓ」（Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ３８ｔｈ Ａｎｎｕａｌ Ａｓｉｌｏｍａｒ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｓｉｇｎａｌｓ， Ｓｙｓｔｅｍｓ ａｎｄ Ｃｏｍｐｕｔｅｒｓ， Ｎｏｖｅｍｂｅｒ ２００４）に、デインターリーブ演算を実行するＧＲＰ命令を２つのバタフライネットワークで並行して実装する方法が記載されている。この出版物では、バタフライネットワークまたは逆バタフライネットワークでＧＲＰを実行することはできないが、２つの逆バタフライネットワークを使用して、ＲビットとＬビットとを並行してグループ化してもよいと述べられている。一方のバタフライネットワークが第１のチャネルをデインターリーブし、他方のバタフライネットワークが第２のチャネルをデインターリーブする。ただし、この技術を使用してインターリーブ演算を実行することはできず、デインターリーブ演算のみ実行することができる。クロスバー配列を使用して汎用的な順列化命令を実行することも公知である。しかし、このようなクロスバーネットワークは、ｎ入力のクロスバーのためにｎ２回の計算命令を伴う。そのため、このようなクロスバーネットワークは、領域効率があまり良くない。]
発明が解決しようとする課題

[0005] そのため、データ順列演算をより効率的に加速する必要がある。また、バタフライ順列ネットワークを使用してインターリーブ演算を実行することも可能である必要がある。]
課題を解決するための手段

[0006] 第１の態様によれば、本発明はデータ処理のための装置を提供し、前記装置は、順列演算を実行するための順列回路を含む、データ処理演算を実行するための処理回路と、データを格納するための複数のレジスタを有するレジスタバンクと、前記処理回路を制御して前記データ処理演算を実行するプログラム命令に応答する制御回路と、を含み、前記制御回路は、ビットマスクに基づいて、前記レジスタバンクの１つ以上のレジスタに格納されるデータを含む入力オペランドで順列演算を実行するための前記順列回路を構成する制御信号を生成する制御生成命令に応答するように構成され、前記ビットマスクは、第１の順序を有する第１のグループのデータ要素と第２の順序を有する第２のグループのデータ要素とを前記入力オペランド内で特定し、前記順列演算は、前記第１の順序と前記第２の順序とのうちの一方を保存するが、他方を変える。]
[0007] 本発明は、第１の順序を有する第１のグループのデータ要素と、第２の順序を有する第２のグループのデータ要素とを含む入力オペランドで順列演算を実行し、第１の順序と第２の順序とのうちの一方を保存して他方を変えることにより、ビットマスクを基に制御回路を使用し、制御信号を生成して順列演算を実行するための順列回路を構成して、より効果的な順列演算を実行できることを認める。このような順列演算の実行を可能にする制御生成命令を提供することにより、順列回路の構成に大きな柔軟性が提供され、より領域効率的に順列演算を実行することが可能となる。また、データ再配置が高データレートで実行された場合にデータ再配置がボトルネックになるという課題を改善する。]
[0008] 順列演算に伴う入力オペランドの第１の順序と第２の順序とのうちの一方の順序変更は、入力順序に関連する数々の異なる順序変更のいずれか１つを含み得ることは理解されよう。ただし、一配置において、第１の順序と第２の順序とのうちの一方の順序変更は、逆順化を含む。配列された２つのデータセットの一方の逆順化により、その２つのデータセットのデータを入力順序に従って手軽に分離し、簡単に並べ替えることができる。さらに、第２のデータセットの逆順化により、順列回路が簡略化される。]
[0009] 順列演算が、単純再配列やデータの逆順化など、数々の異なる順列演算のいずれかであり得ることは理解されよう。ただし、一実施形態において、順列演算は、インターリーブ演算とデインターリーブ演算とのうちの一方である。一般にこれらの演算は、信号処理アプリケーションで実行されており、本技術に係る順列回路と制御回路とを使用した効率的な実装は、全体の処理スループットを高める可能性が高い。]
[0010] 制御生成命令の目的が、順列演算を実行するための順列回路の構成のみということもあり得るという点は理解されよう。別の命令を用意して実際に順列回路を制御し、順列演算を実行してもよい。ただし、一実施形態において、制御回路は、制御生成命令に応答して順列回路を構成し、順列演算を実行する。これにより、順列演算が便利に実装される。単一命令の使用により、一般的な演算の実行が簡略化され、プログラムコードを簡潔にすることができる。]
[0011] 入力オペランドのデータ要素がシングルビットデータ要素である可能性があることは理解されよう。ただし、一実施形態において、入力オペランドのデータ要素はマルチビットデータ要素を含む。シングルビットデータ要素ではなくマルチビットデータ要素を順列化するには、メモリアクセスを減らす必要があり、それによって効率が上がる。]
[0012] 入力オペランドまたは順列演算が、スカラや標準ベクトルなど、任意のタイプの入力オペランドを含み得ることは理解されよう。ただし、一実施形態において、入力オペランドは、例えば複数の通信チャネルからのデータを含むパックドベクトルを含む。パックドベクトルの使用により、計算が並行処理され、それによって処理が加速する。]
[0013] 順列演算に対する入力オペランドがスカラを含み得ることは理解されよう。同様に、順列演算によって生成される出力値は、スカラ値を含み得る。ただし、一実施形態において、順列演算は、２つの配列されたデータセットを含む入力ベクトルデータに対して実行され、保存された順序を有する前記第１および第２のグループのデータ要素の一方と、変更された順序を有する前記第１および第２のグループデータ要素の他方とを含む出力ベクトルを生成する。ベクトル処理により、所与の計算を実行するために必要なメモリアクセスの回数が減り、それによって計算の効率が上がる。]
[0014] 入力ベクトルはメモリから直接入力され得ることは理解されよう。ただし、一実施形態において、入力ベクトルは複数のベクトルレジスタを含み、出力ベクトルはそれぞれの複数のベクトルレジスタを含む。このような方法でのレジスタの使用により、データへのアクセス性が向上し、それによって計算のスループットが増加する。]
[0015] データ処理装置により、ビットマスクをメインメモリなど任意の場所に格納できることは理解されよう。ただし、一実施形態において、データ処理装置は、ビットマスクを格納するための少なくとも１つのマスクレジスタを含む。特殊目的のマスクレジスタは、順列演算を実装しやすくする。]
[0016] 少なくとも１つのマスクレジスタが、第１のグループのデータ要素と第２のグループのデータ要素とを区別する数々の異なる方法のいずれか１つで構成され得ることは理解されよう。ただし、一実施形態において、少なくとも１つのマスクレジスタは、０ビットを使用して第１のグループのデータ要素と第２のグループのデータ要素とのうちの一方を表し、１ビットを使用して２つのデータ要素のグループの他方を表す。代替実施形態において、少なくとも１つのマスクレジスタは、ブールレジスタである。このタイプのマスクレジスタは実装しやすく、そのため、データ処理装置の組み立てが簡略化される。]
[0017] 順列回路は、順列演算を実行できるという条件で、数々の異なる形態のいずれか１つを取り得ることは理解されよう。ただし、一実施形態において、順列回路は、データ要素ペア間のバタフライ接続に基づいて、複数のデータ要素を再配置するように構成されたバタフライネットワークを含む。順列回路をバタフライネットワークとして実装すれば、ｎ入力計算をｌｏｇ ｎ段階で実行することが可能となるため、特に効率的である。これは、例えば、ｎ入力計算のためにｎ２段階を必要とするクロスバーネットワークと比べて好ましい。バタフライネットワークは、構成しやすく、効率的に実装できる。順列回路をバタフライネットワークとして実装することにより、インターリーブ演算とデインターリーブ演算との両方を実行する目的で単一のバタフライネットワークを実装することができる。これは、バタフライネットワークを使用して、（インターリーブではなく）デインターリーブ演算しか実行できず、デインターリーブ演算を実行するために少なくとも２つの別々のネットワークが必要であった既知のシステムと比べて好ましい。単一のバタフライネットワークを使用できることにより、２つのバタフライネットワークの半分の電力で計算を実行することができる。]
[0018] バタフライネットワークは、データ要素が一定でバタフライが変化するインプレース型のバタフライネットワークであり得ることは理解されよう。ただし、一実施形態において、バタフライネットワークは、バタフライ接続が一定であり、複数のデータ要素が移動できる一定ジオメトリのネットワークである。]
[0019] 第１および第２のグループのデータ要素が各々同一数の組成データ要素を有し得ることは理解されよう。ただし、一実施形態において、第１のグループのデータ要素と第２のグループのデータ要素とは、異なる数の組成データ要素を有する。これにより、極めて柔軟に順列計算を実行できるようになり、より多様なインターリーブおよびデインターリーブ演算が実行できるようになる。]
[0020] 第１のグループのデータ要素と第２のグループのデータ要素とが単一ソースからのデータを含み得ることは理解されよう。ただし、一実施形態において、第１のグループのデータ要素と第２のグループのデータ要素とは、２つの異なる通信チャネルにそれぞれ対応する。これにより、２つの異なる通信チャネルのインターリーブとデインターリーブとが容易になり、一般的な信号処理演算を効率よく処理することができる。]
[0021] データ処理装置が数々の異なる形態のいずれか１つを取り得ることは理解されよう。例えば、データ処理装置は、中央処理装置（ＣＰＵ）であってもよい。ただし、一実施形態において、データ処理装置は、デジタル信号プロセッサである。代替実施形態において、データ処理装置は、コプロセッサである。]
[0022] 第２の態様によれば、本発明は、データ処理演算を実行するための処理回路を有するデータ処理装置と、データを格納するための複数のレジスタを有するレジスタバンクと、前記処理回路を制御して前記データ処理演算を実行するプログラム命令に反応する制御回路とを使用して順列演算を実行するための方法を提供し、前記制御回路は、順列演算を実行するための順列回路を含み、前記方法は、（ｉ）制御生成命令に対し、ビットマスクを基に制御信号を生成して、前記レジスタバンクの１つ以上のレジスタに格納されるデータを含む入力オペランドで順列演算を実行するための前記順列回路を構成する制御信号を生成するステップを含み、前記ビットマスクは、第１の順序を有する第１のグループのデータ要素と第２の順序を有する第２のグループのデータ要素とを前記入力オペランド内で特定し、前記順列演算は、前記第１の順序と前記第２の順序とのうちの一方を保存するが、他方を変える。]
[0023] 第３の態様によれば、本発明は、データを処理するための装置のエミュレーションを提供する仮想マシンを提供し、前記装置は、順列演算を実行するための順列回路を含む、データ処理演算を実行するための処理回路と、データを格納するための複数のレジスタを有するレジスタバンクと、前記処理回路を制御して前記データ処理演算を実行するプログラム命令に応答する制御回路と、を含み、前記制御回路は、ビットマスクに基づいて、前記レジスタバンクの１つ以上のレジスタに格納されるデータを含む入力オペランドで順列演算を実行するための前記順列回路を構成する制御信号を生成する制御生成命令に応答するように構成され、前記ビットマスクは、第１の順序を有する第１のグループのデータ要素と第２の順序を有する第２のグループのデータ要素とを前記入力オペランド内で特定し、前記順列演算は、前記第１の順序と前記第２の順序とのうちの一方を保存するが、他方を変える。]
[0024] 本発明の他の様々な態様および特徴が、添付の請求の範囲においてそれぞれ定められる。従属請求項の特徴の組み合せは、独立請求項の特徴と適宜組み合わせることができ、請求項に明記されているだけにとどまらない。]
[0025] 以降、本発明の実施形態を、添付の図面を参照しながら一例として記載する。]
図面の簡単な説明

[0026] 本発明の一実施形態に係るデータ処理装置を示す模式図である。
本技術に係るベクトルデインターリーブ命令を示す模式図である。
本技術に係るベクトルインターリーブ命令を示す模式図である。
図２Ａおよび２Ｂのベクトルインターリーブ命令ＶＩＴＬとベクトルデインターリーブ命令ＶＤＴＬとを実装する際に図１のバタフライ順列ネットワークによって実行される一連の順列化を示す模式図である。
既知のシステムでデインターリーブ演算を実装するのに２つの別々のバタフライネットワークが必要であった理由を示す模式図である。
８要素のビットマスクの実施例において制御ジェネレータ１１６の制御回路の具体的な実施形態を示す模式図である。
制御値ｉが０に等しく、入力マスクｍが［１１００１１１０］に等しいケースを表す図である。
入力マスクの値を示す図であり、上記計算では、制御段階ｉの出力制御ビットは１に等しい。
ｉが論理ゲートの各々に対応する入力および出力を有する２段階計算に等しいことを示す図である。
１６ビットマスクを例に制御生成回路を示す模式図である。
本発明の一実施形態に係る制御生成命令ＶＤＴＬＣをＣプログラミング言語で記したプログラムコードを示す図である。
例示的なデインターリーブ命令のプログラムコードを示す図である。
インターリーブ再配置命令と関連付けられているプログラムコードを示す図である。
所与のデインターリーブ演算用の一定ジオメトリのバタフライ回路を示す模式図である。
所与のデインターリーブ演算用のインプレース型のバタフライ回路を示す模式図である。
図１のデータエンジン１００の仮想マシンの実装を示す模式図である。] 図１ 図２Ａ
[0027] 図１は、本発明の一実施形態に係るデータ処理装置を示す模式図である。装置は、バタフライ順列ネットワーク１１０と、ＳＩＭＤレジスタ１１２と、マスクレジスタバンク１１４と、制御ジェネレータ１１６と、を有するデータエンジン１００を含む。データ処理装置は、データメモリ１２０と、コントローラ１３０と、命令メモリ１４０とを、データエンジンに対して外部的にさらに含む。] 図１
[0028] バタフライ順列ネットワーク１１０は、ＳＩＭＤレジスタ１１２から読み込まれた複数のマルチビットデータ要素を有するパックドベクトルを含む入力値サンプルに対して順列演算を実行する。ＳＩＭＤレジスタの幅は、各々３２×１６ビット要素である。順列演算のための入力ベクトルは、レジスタペア、すなわち６４×１６ビット要素を１度に使用して実行される。順列化の結果は、ＳＩＭＤレジスタバンク１１２へと書き戻される。データエンジン１００の処理回路は、命令メモリ１４０から読み込まれたプログラム命令の実行に応じてデータ処理演算を実行する。コントローラ１３０はそれらの命令を、データエンジン１００の処理回路を制御してデータ処理演算を実行する制御信号に変換する。ただし、バタフライ順列ネットワーク１１０は、データエンジン１００内で制御ジェネレータ回路１１６によって生成される制御信号によってさらに制御される。]
[0029] 特に制御ジェネレータ１１６は、３２ビットマスクレジスタバンク１１４から読み込まれる入力ビットマスクに基づいて、バタフライ順列ネットワーク１１０を構成するための制御信号を生成する。制御ジェネレータ回路１１６は、生成された制御信号を出力し、それらをマスクレジスタバンク１１４に格納する。制御信号は、マスクレジスタバンク１１４から読み込まれ、関連する順列演算を実行するために、適時にバタフライネットワークに供給される。]
[0030] 順列演算の結果ベクトルは、６４×１６ビットデータ要素を含む「パックド(packed)」ベクトルである。マスクレジスタバンク１１４によって制御ジェネレータ回路１１６に適用されるビットマスクは、第１の順序を有する第１のグループのデータ要素と、第２の順序を有する第２のグループのデータ要素とを入力ベクトル内で特定する役割を果たす。例えば、第１のグループのデータ要素は第１の通信チャネルのデータに対応し得るのに対し、第２のグループのデータ要素が２つ目の通信チャネルに対応する。順列演算は３２×１６ビットのレジスタペアを使用して実行されるため、制御ジェネレータ１１６は、３２ビットマスクレジスタを読み込んで、順列化される６４要素内で２つのデータセットを特定するのに必要な６４マスクビットを取得する。制御ジェネレータ１１６によって生成される制御信号は、入力ベクトルに対して実行される順列演算が第１の順序と第２の順序とのうちの一方を保存して他方を変えるようにバタフライネットワークを構成する。ＳＩＭＤレジスタとマスクレジスタのデータ値は、外部データメモリ１２０から読み込まれてもよい。制御ジェネレータ回路１１６によって出力される特定の制御信号は、複数のマスクベクトルのうちどれが制御ジェネレータ回路１１６に入力値として供給されるかによって変わってくる。順列ネットワーク１１０は、合計３２個の１６ビットデータ要素を含むパックドベクトルに対して動作する。]
[0031] 図２Ａおよび２Ｂは、本技術に係るベクトルデインターリーブ命令とベクトルインターリーブ命令とを示す模式図である。] 図２Ａ
[0032] 図２Ａは、複数のデータ要素を含む入力ベクトルＶｎを、ビットマスクＶｍに従って、チャネル０のサンプルと逆転されたチャネル１のサンプルとを含む出力ベクトルＶｄに再配置するベクトルデインターリーブ命令を示す模式図である。チャネル０のサンプルはｘ０、ｘ１、ｘ２で表され、チャネル１のサンプルはｙ０、ｙ１、ｙ２、ｙ３、およびｙ４で表される。この実施例において、ベクトルは８つのデータ要素を含み、各々がマルチビットデータ要素である。ただし、ビットマスクＶｍは、ベクトルの８つのデータ要素に対応する合計８つのビットを含む。このベクトルデインターリーブ命令ＶＤＴＬは、図１のＳＩＭＤレジスタバンク１１２から読み込まれる８データ要素の入力ベクトル２２０に対して動作し、図１のバタフライ順列ネットワーク１１０は、順列化によってチャネル０のサンプルがチャネル１のサンプルから分離されるように、ビットマスク２１０に基づいて構成される。したがって、出力ベクトル２３０は、チャネル０のサンプルｘ０、ｘ１、およびｘ２が順に出力され、チャネル１のサンプルｙ４、ｙ３、ｙ２、ｙ１、およびｙ０が逆の順序で出力されるパックドベクトルである。ビットマスク２１０は、チャネル０のサンプルに対応するビット値０を有し、チャネル１のサンプルに対応するビット値１を有することがわかる。したがって、ビットマスク２１０により、バタフライ順列回路１１０が、２つのチャネルの分離を実行するためにチャネル０のサンプルとチャネル１のサンプルとを区別することが可能になる。] 図１ 図２Ａ
[0033] 図２Ｂは、本発明の一実施形態に係るベクトルインターリーブ命令ＶＩＴＬを示す模式図である。このベクトルインターリーブ命令は、チャネル０とチャネル１とのサンプルを含む８データ要素(eight data-element)の入力ベクトル２２２に対して動作する。このケースでは、チャネル０のサンプルが、入力ベクトルＶｎにて連続的に配置されており、チャネル１のサンプルも同様である。ビットマスク２１２は、インターリーブ演算がどのように実行されるべきかを示す。特に、チャネル０のサンプルの然るべき配置場所に対応する出力ベクトルＶｄ内の位置が、対応するビットマスクの位置に０を有するのに対し、チャネル１のサンプルが配置されるべき出力ベクトル内の位置は、対応するビットマスクの位置に１を有する。そのため、出力ベクトル２３２は、チャネル０のデータ要素ｘ０、ｘｌ、およびｘ２が、チャネル１のデータ要素ｙ０、ｙ１、ｙ２、ｙ３、およびｙ４によってインターリーブされる。図２Ｂの出力ベクトル２３２のこのケースでは、左から右にベクトルを読み込むと、チャネル１のサンプルと同様、チャネル０のサンプルも昇順で配置される。これは、ベクトルデインターリーブ演算の出力ベクトル２３０とは対照的である。こちらは、出力ベクトル２３０で左から右に読み込むと、チャネル０のサンプルが昇順で配置されるのに対し、チャネル１のサンプルは降順に配置される。それでも、図２Ａと図２Ｂとの両方で、チャネル０のデータ要素の配列は、入力ベクトルＶｎと出力ベクトルＶｄとの間で維持されるのに対し、チャネル１のサンプルの配列は、入力ベクトルＶｎと出力ベクトルＶｄとの間で逆になる。チャネル１のサンプルの順序は入力順序に対して出力時に逆になるものの、２つのチャネルの分離後に、チャネル１のサンプルの順序を逆にしてベクトル（またはレジスタ）全体の入力順序を一度に取得するのは比較的容易である。この例示的な実施形態において、ビットマスクレジスタは、ブール値(Boolean value)（すなわち述語(predicate)）のレジスタである。ただし、代替実施形態では、ビットマスクレジスタが通常のレジスタである可能性がある。図１の配置において、マスクレジスタバンク１１４は、レーンごとにシングルビットを含むレジスタを有する特別な述語レジスタバンクである。] 図１ 図２Ａ 図２Ｂ
[0034] 図３は、図２Ａおよび２Ｂのベクトルインターリーブ命令（ＶＩＴＬ）とベクトルデインターリーブ命令（ＶＤＴＬ）を実行する際に、図１のバタフライ順列ネットワーク１１０によって実行される一連の順列化を示す模式図である。バタフライネットワークは、データ順列化の実行時に使用するのに適した魅力的な性質を有する。このケースでは、バタフライネットワークが８つの入力データ要素を有し、順列化を、第１の段階３１０と、第２の段階３２０と、第３かつ最終の段階３３０という３つの個別段階に分割することができる。一般に、ｎ入力バタフライネットワークにおける段階の合計数はｌｏｇ ｎであり、交点の合計数はｎ ｌｏｇ ｎである。これは、ｎ入力クロスバーネットワークの場合に生まれるｎ２か所の交点より大幅に少ない。したがって、バタフライネットワークの回路実装は、標準的なクロスバーより領域効率に優れている。図３の実施例には、合計２４か所の交点がある。バタフライネットワークの各段階で、入力値ごとに、２つの同じ出力を共有する別の入力値がある。本願明細書では、これらの入力値ペアを共有入力値と称し、対応する出力値ペアを共有出力値と称する。バタフライネットワークにおけるこれらの共用ペアは、シングルビットを使用して構成される。例えば、バタフライネットワークの第１段階において、データ要素の入力値ペアｘ０、ｙ０は、その直下に、第１段階で破線の交点によって示される共有出力値を有する共有入力値である。このケースでは、データ入力要素ｘ０とｙ０とが、第１段階の終わりの時点では既存の位置にとどまっている（すなわち、破線の交点経路ではなく、垂直経路をたどる）。ただし、バタフライネットワークの構成が異なっていれば、これら２つのデータ要素が場所をスワップしていた可能性がある。] 図１ 図２Ａ 図３
[0035] バタフライネットワークの第２段階３２０において、入力データ要素ｙ０は、第２段階の出力時に入力データ要素ｙ０と位置をスワップし、データ要素ｘ２とｙ３も位置をスワップする。このケースでは、第１段階３１０が入力と出力との間で１か所水平にシフトする可能性を伴い、第２段階が２か所の水平スワップを伴い、第３段階が４か所の水平スワップを伴うことに注意されたい。いずれのケースでも、入力データ要素は、出力時に、該当する入力段階のときと同じ位置に留まっていてもよい。入力段階３１０から、８データ要素の入力ベクトル［ｘ０，ｙ０，ｙ１，ｙ２，ｘ１，ｘ２，ｙ３，ｙ４］は図２Ａの入力ベクトル２２０に対応し、デインターリーブ命令を実装する際に伴う３段階の順列化は、第３段階３３０の出力が図２Ａの出力ベクトル２３０に対応するように図３のバタフライ順列ネットワークで最上部から最下部までたどることによって追跡可能であることがわかる。逆に、図３のバタフライネットワークの最下部から始め、段階３３０から段階３２０を経由して最終的に段階３１０に戻ることは、図２Ｂのベクトルインターリーブ命令ＶＩＴＬを実装することに対応する。] 図２Ａ 図２Ｂ 図３
[0036] 図２Ａおよび図２Ｂのベクトルインターリーブ命令に対応する制御ビットは、図３のバタフライダイアグラムに由来する可能性がある。各段階のすべてのデータスワップが実線で示されており、スワップが発生しないところでは、破線が引かれているという点に注意されたい。したがって、制御ビットを右から左に読むと、段階３１０の制御ビットは［０，１，０，０］、段階３２０の制御ビットは［０，１，１，０］となり、段階３３０の制御ビットは［１，１，１，０］となる。ベクトルインターリーブ命令とベクトルデインターリーブ命令との両方が、単一のバタフライ順列ネットワークを使用して実行されたことに注意されたい。既知のシステムでは、バタフライネットワークを使用してインターリーブ演算を実行することが全く知られておらず、さらに、バタフライネットワークを使用してデインターリーブ演算を実行するには、図４に示すとおり、少なくとも２つの異なるバタフライネットワークを連続して、または横並びにして使用して実装するしかない。] 図２Ａ 図２Ｂ 図３ 図４
[0037] 図４は、既知のシステムでデインターリーブ演算を実装するのに２つの別々のバタフライネットワークが必要である理由を示す模式図である。図４は、チャネル０のサンプル用の第１のバタフライネットワーク４００と、チャネル１のサンプル用の第２のバタフライネットワーク４５０を示す図である。図２Ａに示す本発明の実施形態との整合を保つために、インターリーブされた同じ８要素の入力ベクトルが使用されている。ただし、チャネル０のサンプルだけは第１のバタフライネットワーク４００にあり、チャネル１のサンプルは第２のバタフライネットワーク４５０に示されている。既知のシステムでは、チャネル０のサンプルとチャネル１のサンプルの出力は、両方のチャネルサンプルデータの順序が出力時に保存されるようになっていた。特に、入力順序はそれぞれｘ０、ｘ１、ｘ２およびｙ０、ｙ１、ｙ２、ｙ３、ｙ４であり、出力順序は同一である。所与のチャネルに対応するデータ要素は、入力時でなく出力時に連続的に配置される。] 図２Ａ 図４
[0038] 図３において、バタフライダイアグラムの破線はスワップを表し、実線は実行中のスワップを表していたことに注意されたい。しかし、図４、図１０Ａ、および０１Ｂのダイアグラムでは、すべての線が実線である。これらのダイアグラムにおいて、それぞれの実線の交点は、（交点に従って）要素がスワップされる可能性があるか、入力制御ビットに応じて同じ位置にとどまる可能性があることを意味する。] 図１０Ａ 図３ 図４
[0039] 図４のバタフライダイアグラムは、それぞれのケースで出力ベクトルを生成するのに必要な３つの再配置段階を示す。単一のバタフライ順列ネットワークを使用してこのデインターリーブ演算を実行することはできないという事実は、各々のバタフライネットワークの段階２の出力から明らかである。そこでは、データ要素の必須出力位置に２つの衝突４１０、４２０が存在することが示されている。特に衝突４１０は、第１のバタフライネットワークに最も左の位置を有する要素ｘ０を伴う。この要素は、第２のバタフライネットワーク４５０のデータ要素ｙ１によっても必要とされる。同様に、バタフライネットワーク４００の右からの２つ目のデータ要素、すなわちデータ要素Ｘ２が、第２段階の出力でチャネル１のデータ要素Ｙ３と衝突する。Ｙ３が出力ベクトルの所望の最終順序を実現するには、ｘ２と同じ出力位置に存在する必要がある。図３と図４とを比較することにより、本技術に従って順列化を実行することにより、結果的に効率が改善されることがわかる。チャネル１のデータが出力時に逆の順序になることを許可することにより、単一のバタフライネットワークを使用して計算を実行することができる。さらに、デインターリーブ演算だけでなく、インターリーブも快適かつ効率的に実行することができる。] 図３ 図４
[0040] 図５Ａは、８要素ビットマスクの場合の図１の制御ジェネレータ１１６の制御回路の具体的な実施形態を示す模式図である。制御回路５００の出力値は、制御ビットＣｉ［０］、Ｃｉ［ｌ］、Ｃｉ［２］、およびＣｉ［３］を表す。これらの４つの制御ビットは、図３のバタフライ順列ネットワークの段階「ｉ」の構成ビットに対応する。制御ビットは、８ビットマスクに基づいて生成される。回路は、４つの排他的ＯＲ（ＸＯＲ）ゲート５０２、５０４、５０６、５０８を１セット含む。マスクビットｍ［０］とｍ［１］とが第１のＸＯＲゲート５０２に入力され、マスクビットｍ［２］とｍ［３］とがＸＯＲゲート５０４に入力され、マスクビットｍ［４］とｍ［５］とがＸＯＲゲート５０６に入力され、マスクビットｍ［６］とｍ［７］とがＸＯＲゲート５０８に入力される。] 図１ 図３ 図５Ａ
[0041] ＸＯＲゲート５０２の出力値は、制御値ｉが１未満であるか１に等しいかによって異なる入力値と共にＡＮＤゲート５１０に供給される。ＡＮＤゲート５１０の出力値は、第２のＸＯＲゲート５２２と第３のＸＯＲゲート５３２とに供給される。ＸＯＲゲート５３２の出力値は、制御ビットＣｉ［１］を表す。制御ビットＣｉ［０］は、マスクビットｍ［０］に直接対応する。ＸＯＲゲート５２２の第２の入力値は、ＸＯＲゲート５０４の出力値に対応する。ＸＯＲゲート５２２の出力値は、制御ビットｉが０未満か０に等しいかによって異なる入力値と共に、ＡＮＤゲート５２６に供給される。ＡＮＤゲート５２６の出力値は、マスクビットｍ［４］と共にＸＯＲゲート５３４への入力値として供給される。ＸＯＲゲート５３４の出力値は、制御ビットＣｉ［２］に対応する。]
[0042] ＡＮＤゲート５２６の出力値は、ＸＯＲゲート５２９へのさらなる入力値としても供給され、ＸＯＲゲート５２９の出力値は使用されない。ＡＮＤゲート５２６の出力値は、ＸＯＲゲート５２８にさらに供給され、ＸＯＲゲート５２８の出力値は、マスクビットｍ［６］と共にさらなるＸＯＲゲート５３６に供給される。このＸＯＲゲート５３６の出力値は、制御ビットＣｉ［３］に対応する。ＸＯＲゲート５０６の出力値は、制御ビットｉが１未満か１に等しいかによって異なる入力値と共にＡＮＤゲート５１２に供給される。このＡＮＤゲート５１２の出力値は、ＸＯＲゲート５２８への入力とＸＯＲゲート５２４への入力値との両方として適用される。]
[0043] したがって、制御回路５００は、複数のＸＯＲゲートと複数のＡＮＤゲートとを含むことにより、出力制御ビットがマスクビットと制御値ｉとの両方に依存するようになっている。図５Ａの回路の各段階における値の具体的な実施例を、図５Ｂ、５Ｃ、および５Ｄの実施例に示す。] 図５Ａ 図５Ｂ
[0044] 実施例 ｎ＝２で、初期入力マスクｍ＝［１ １ ０ ０ １ １ １ ０］である入力２ｎ＋１ビットマスク
ｉ＝０ Ｃ０［ ］＝［０ １ ０ ０］
次の段階の入力マスクｍ［ ］ ＝ ［１ ０ １ １ １ ０ １ ０］
ｉ＝１ Ｃ１［ ］＝［０ １ １ ０］
次の段階の入力マスク ｍ［ ］ ＝ ［１ １ ０ １ ０ １ １ ０］
ｉ＝２ Ｃ２［ ］＝［１ １ １ ０］
次の段階の入力マスク ｍ［ ］＝［１ ０ ０ １ １ １ １ ０］]
[0045] 図５Ｂは、制御ビットｉ＝０で、入力ビットマスクｍ＝［１１００１１１０］であるケースを表す。図５Ｂのダイアグラムに、論理ゲートの各々の論理出力が示されている。このケースでは、ｉ＝０であり、ｉ≦１を満たしているため、ＡＮＤゲート５１０、５１２、および５２６への制御依存入力値はすべて、０ではなく１の値を取る。上記入力マスクによって生成される制御ビット出力値は、４ビット制御値Ｃ０［ ］＝［０，１，０，０］に対応することがわかる。] 図５Ｂ
[0046] 図５Ｃは、上記計算における入力マスクの値と、ｉ＝１の場合の出力制御ビットを示す。このケースでは、入力マスクがｍ＝［１０１１１０１０］に対応する。すなわち、段階ｉ≧０以上でない場合の入力ビットマスクである。段階ｉ＝１で生成される制御ビットは、図示のとおりＣ１［ ］＝［０，１，１，０］である。このケースでは、ｉ＝１（したがって条件ｉ≦１が満たされている）であるため、ＡＮＤゲート５１０と５１２とへの制御依存入力値は０ではなく１であるが、ＡＮＤゲート５２６への制御依存入力値は０である。] 図５Ｃ
[0047] 図５Ｄは、ｉ＝２の段階の計算と、論理ゲートの各々に対応する入力値と出力値とを示す。このケースでは、入力ビットマスクｍ［ ］＝［１１０１０１１０］であり、これはｉ≧１でない場合のビットマスクである。この段階＝２で生成される出力値は、制御ビットＣ２［ ］＝［１，１，１，０］である。このケースでは、ｉ＝２であるため、ＡＮＤゲート５１０、５１２、および５２６の各々への制御依存入力値は０である（条件ｉ≦１が満たされないため）。] 図５Ｄ
[0048] 図６は、ｎ＝３、すなわち１６データ要素の入力ベクトルおよびマスクの場合の制御ジェネレータ１１６の制御回路の代替実装を示す模式図である。図５Ａの回路に関しては、回路がＸＯＲゲートとＡＮＤゲートとの配列を含む。出力制御値は、マスクビットと制御値（すなわちｉの値）との両方に依存する。図１の制御ジェネレータ回路１１６は、以下のアルゴリズムを実装して、以降の計算段階で使用される出力マスクベクトルを計算する。] 図１ 図５Ａ 図６
[0049] 制御生成(CONTROL GENERATION)
入力 ２ｎ＋１ビットマスク（ｍ［２ｎ＋１−１］．．．．ｍ（０））
出力 各々２ｎビットの（ｎ＋１）制御マスク（Ｃｉ［２ｎ−１］．．．．Ｃｉ［Ｏ］）
アルゴリズム
ｆｏｒ ｉ＝０，１，２，．．．．ｎ

｛
Ｃｉ［２ｎ−１］．．．．Ｃｉ［０］は、制御段階回路によって生成される制御マスクである。
（Ｃｉ［Ｋ］なら、各々のＫ＝２ｎ−１，．．．０につきｍ［２Ｋ＋１］とｍ［２Ｋ］とをスワップ
（ｍ［２ｎ＋１−１］．．．．ｍ［０］←（ｍ［２ｎ＋１−１］ ｍ［２ｎ＋１−３］．．．ｍ［１］
ｍ［２ｎ＋１−２］ ｍ［２ｎ＋１−４］．．．ｍ［０］）
と並べ替え
｝
注：これは、ｍを再利用するか、中心ステップ回路をｎ回チェーン化することによって連続的に実装することができる。
７ ６ ５ ４ ３ ２ １ ０
例 ｎ＝２ ｉ＝０，１，２ ｍ＝［１ １ ０ ０ １ １ １ ０］と仮定すると、
３ ２ １ ０
ｉ＝０につきＣ０［ ］＝［０ １ ０ ０］であることから、
Ｃ０［２］のみ＃０となる。
∴ ｍ［５］とｍ［４］とをスワップ → 変化なし
［ｍ７ ｍ６ ｍ５ ｍ４ ｍ３ ｍ２ ｍ１ ｍ０］を並べ替え
→ ［ｍ７ ｍ５ ｍ３ ｍ１ ｍ６ ｍ４ ｍ２ ｍ０］
［１ ０ １ １ １ ０ １ ０］＝段階ｉ＝０の場合のｍ出力の値]
[0050] 図６の回路は、２の乗数である任意のマスクサイズに容易に拡張できることに注意されたい。] 図６
[0051] 図７は、本発明の一実施形態に係る、Ｃプログラミング言語による制御生成命令ＶＤＴＬＣのプログラムコードを示す。制御生成命令ＶＤＴＬＣは、入力値として３２ビットブール値ＶＢＯＯＬ１６＿Ｔ Ｘ０、６４ビットビットマスクとしてＶＢＯＯＬ１６＿Ｔ Ｘ１を取り、図１のバタフライ順列ネットワーク１１０を構成するための制御ビットを含む出力値を生成する。このプログラムコードは、特定マスクビットのスワップとマスクの並べ替えによる次の計算段階用の入力マスクの生成を伴う上記の制御生成アルゴリズムを実装する。] 図１ 図７
[0052] 図８は、デインターリーブ再配置命令と具体的に関連付けられているプログラムコードを示す。] 図８
[0053] 図９は、インターリーブ再配置命令と関連付けられているプログラムコードである。] 図９
[0054] 図２Ａおよび図２Ｂに示される再配置演算の各々を実装するために、単一の原子的な（ａｔｏｍｉｃ）プログラム命令が使用できる可能性もある。あるいは、２つ以上のプログラム命令の組み合せを使用して、所与の入力ベクトルを基に必要な出力ベクトルを生成できる可能性もある。特に、記載されている実施形態においては、別々の制御生成命令を使用して制御信号が生成され、以降の再配置命令を使用してインターリーブまたはデインターリーブ再配置が実行される。制御生成とインターリーブまたはデインターリーブ演算とを代替実施形態の単一プログラム命令の中で組み合わせられる可能性があることは理解されよう。] 図２Ａ 図２Ｂ
[0055] 図３に模式的に示すバタフライネットワークは、一実施例装置であるにすぎない。上記の制御信号生成は、一定ジオメトリのバタフライで使用する制御信号を生成する。一定ジオメトリのバタフライ順列ネットワークでは、同じ要素ペアが常にスワップされるが、要素自体は移動して異なる出力値を生成する。代替実施形態では、高速フーリエ変換（ＦＦＴ）スタイルのバタフライ順列化作業が使用される。ここでは、データ要素は一定であるものの、再配置を実行するためにバタフライ接続自体は変化する。] 図３
[0056] 図１０Ａは、所与のデインターリーブ演算用の一定ジオメトリのバタフライ回路を示す模式図であり、図１０Ｂは、同じデインターリーブ演算用のインプレース型バタフライ回路を示す模式図である。各段階の制御信号が図１０Ａと図１０Ｂとで同じだが、各段階で実行されるスワップは２つのダイアグラムで異なることがわかる。図１０Ａと図１０Ｂとの回路は同じである。すなわち、同じ接続を有するが、物理的な二次元レイアウトは異なる。ただし、図１０Ａの配置については、第１の層のゲートだけを使用し、３サイクルで３回それらを再利用するというオプションがある。一般に、制御信号はこの２つの回路で順序が異なるが、示されている実施例の制御値セットについては該当しない。] 図１０Ａ 図１０Ｂ
[0057] 上記の技術は、上述の命令を含む一連のネイティブ命令を実行するハードウェアによって実行されてもよい一方、代替実施形態では、このような命令が、仮想マシンにとってネイティブであるような仮想マシン環境で実行してもよいことは理解されよう。ただし仮想マシンは、異なるネイティブ命令セットを有するハードウェア上で実行しているソフトウェアによって実装される。バーチャルマシン環境は、完全な命令セットの実行をエミュレートする完全なバーチャルマシン環境を提供しても良く、または、本技術の命令を含む一部の命令だけがハードウェアによってトラップされ、部分的な仮想マシンによってエミュレートされる部分的な環境を提供しても良い。]
[0058] より詳細には、上記の制御生成命令を、完全または部分的仮想マシンに対するネイティブ命令として実行し、仮想マシンとその基底ハードウェアプラットフォームを併用して、上記の処理回路と制御回路とを提供してもよい。]
実施例

[0059] 図１１は、図１のデータエンジン１００の仮想マシンの実装を示す模式図である。この構成は、データエンジン１００の演算をエミュレートするように構成された仮想マシン１１００を含む。仮想マシン１１００（ＡＲＭプロセッサまたはデータエンジンのエミュレートなど）は、自らが実行をエミュレートする本技術にかかる制御生成命令を含むマシンコード（ＡＲＭマシンコードなど）を受け取るように構成される。仮想マシンの演算に使用する汎用プロセッサが十分に高性能であれば、現実的な全体の処理スループットを実現することができ、本技術に係る制御生成命令を含む既存のコードベースを実行できるという効果により、汎用プロセッサのこのような使用が正当化されるであろう。] 図１ 図１１
[0060] １００データエンジン
１１０バタフライ順列ネットワーク（順列回路）
１１２ＳＩＭＤレジスタ
１１４マスクレジスタバンク（マスクレジスタ）
１１６ 制御ジェネレータ
１２０データメモリ
１３０コントローラ
１４０ 命令メモリ]

权利要求:

請求項1
データを処理するための装置であり、順列演算を実行するための順列回路を含む、データ処理演算を実行するための処理回路と、データを格納するための複数のレジスタを有するレジスタバンクと、前記処理回路を制御して前記データ処理演算を実行するプログラム命令に応答する制御回路と、を含み、前記制御回路は、ビットマスクに基づいて、前記レジスタバンクの１つ以上のレジスタに格納されるデータを含む入力オペランドで順列演算を実行するための前記順列回路を構成する制御信号を生成する制御生成命令に応答するように構成され、前記ビットマスクは、第１の順序を有する第１のグループのデータ要素と第２の順序を有する第２のグループのデータ要素とを前記入力オペランド内で特定し、前記順列演算は、前記第１の順序と前記第２の順序とのうちの一方を保存するが、他方を変える、データを処理するための装置。
請求項2
前記第１の順序と第２の順序のうち一方の前記変更された順序が逆の順序を含む、請求項１に記載の装置。
請求項3
前記順列演算は、インターリーブ演算およびデインターリーブ演算のうちの１つである、請求項１に記載の装置。
請求項4
前記順列演算は、前記制御生成命令による前記順列回路の構成に従って順列化命令によって実行される、請求項１または請求項２に記載の装置。
請求項5
前記制御回路は、前記制御生成命令に応答して、前記順列回路の構成と前記順列演算の実行との両方を行う、請求項１〜４のうちのいずれか１項に記載の装置。
請求項6
前記データ要素はマルチビットデータ要素を含む、請求項１に記載の装置。
請求項7
前記入力オペランドはパックドベクトルを含む、請求項１〜６のうちのいずれか１項に記載の装置。
請求項8
前記順列演算は、データ要素の前記第１および第２のグループを含むデータの入力ベクトルに対して実行され、保存された順序を有するデータ要素の前記第１および第２のグループのうち一方と、変更された順序を有するデータ要素の前記第１および第２のグループのうち他方と、を含むデータの出力ベクトルを生成する、請求項１〜７のうちのいずれか１項に記載の装置。
請求項9
前記入力ベクトルは複数のベクトルレジスタを含み、前記出力ベクトルはそれぞれの複数のベクトルレジスタを含む、請求項８に記載の装置。
請求項10
前記ビットマスクを格納するための少なくとも１つのマスクレジスタを含む、請求項１〜９のうちのいずれか１項に記載の装置。
請求項11
前記少なくとも１つのマスクレジスタは、０ビットを使用して、前記第１のグループのデータ要素と前記第２のグループのデータ要素とのうちの一方を、１ビットを使用して、前記第１のグループのデータ要素と前記第２のグループのデータ要素とのうちの他方をそれぞれ表す、請求項１０に記載の装置。
請求項12
前記少なくとも１つのマスクレジスタはブールレジスタである、請求項１０記載の装置。
請求項13
前記順列回路は、前記データ要素のペア間のバタフライ接続に基づいて複数のデータ要素を再配置するように構成されたバタフライネットワークを含む、請求項１〜１２のうちのいずれか１項に記載の装置。
請求項14
前記バタフライネットワークは、前記バタフライ接続が一定であり、前記複数のデータ要素が移動を許可されている一定ジオメトリのネットワークである、請求項１３記載の装置。
請求項15
前記バタフライ接続が一定であり、前記複数のデータ要素が移動を許可されている、請求項１３に記載の装置。
請求項16
前記第１のグループのデータ要素と前記第２のグループのデータ要素とが各々の異なる数の構成データ要素を有する、請求項１〜１５のうちのいずれか１項に記載の装置。
請求項17
前記２つの配列されたデータセットが２つの異なる通信チャネルにそれぞれ対応する、請求項１〜１６のうちのいずれか１項に記載の装置。
請求項18
前記データ処理装置はデジタル信号プロセッサである、請求項１〜１７のうちのいずれか１項に記載の装置。
請求項19
前記データ処理装置はコプロセッサである、請求項１〜１８のうちのいずれか１項に記載の装置。
請求項20
データ処理演算を実行するための処理回路を有するデータ処理装置と、データを格納するための複数のレジスタを有するレジスタバンクと、前記処理回路を制御して前記データ処理演算を実行するプログラム命令に応答する制御回路と、を使用して順列演算を実行するための方法であって、前記処理回路は、順列演算を実行するための順列回路を含み、（ｉ）制御生成命令に対し、ビットマスクを基に制御信号を生成して、前記レジスタバンクの１つ以上のレジスタに格納されるデータを含む入力オペランドで順列演算を実行するための前記順列回路を構成する制御信号を生成するステップを含み、前記ビットマスクは、第１の順序を有する第１のグループのデータ要素と第２の順序を有する第２のグループのデータ要素とを前記入力オペランド内で特定し、前記順列演算は、前記第１の順序と前記第２の順序とのうちの一方を保存するが、他方を変える方法。
請求項21
コンピュータを制御して請求項２０に記載の方法を実行するためのコンピュータプログラムを含むコンピュータプログラム製品であって、前記コンピュータプログラムが少なくとも１つの制御生成命令を含む、コンピュータプログラム製品。
請求項22
データを処理するための装置のエミュレーションを提供する仮想マシンであって、前記装置は、順列演算を実行するための順列回路を含む、データ処理演算を実行するための処理回路と、データを格納するための複数のレジスタを有するレジスタバンクと、前記処理回路を制御して前記データ処理演算を実行するプログラム命令に応答する制御回路と、を含み、前記制御回路は、ビットマスクに基づいて、前記レジスタバンクの１つ以上のレジスタに格納されるデータを含む入力オペランドで順列演算を実行するための前記順列回路を構成する制御信号を生成する制御生成命令に応答するように構成され、前記ビットマスクは、第１の順序を有する第１のグループのデータ要素と第２の順序を有する第２のグループのデータ要素とを前記入力オペランド内で特定し、前記順列演算は、前記第１の順序と前記第２の順序とのうちの一方を保存するが、他方を変える、仮想マシン。